package cn.mavor.day0920;

public class LongestDuplicateSubstring {
    public static void main(String[] args) {
        String str1 = "abcfabc";
        String str2 = "afkafk";

        System.out.println("The longest duplicate substring in \"" + str1 + "\" is: \"" + findLongestDuplicateSubstring(str1) + "\"");
        System.out.println("The longest duplicate substring in \"" + str2 + "\" is: \"" + findLongestDuplicateSubstring(str2) + "\"");
    }

    public static String findLongestDuplicateSubstring(String s) {
        int n = s.length();
        long mod = (long)1e9 + 7;
        long base = 26;
        int maxLen = 0;
        long hash = 0;
        long hash2 = 0;
        for (int i = 0; i < n; i++) {
            hash = (hash * base + (s.charAt(i) - 'a' + base)) % mod;
            hash2 = (hash2 * base + (s.charAt(i) - 'a' + base)) % mod;
        }
        for (int len = 1; len <= n / 2; len++) {
            for (int i = 0; i <= n - 2 * len; i++) {
                long hash1 = hash - (s.charAt(i) - 'a' + base) * pow(base, len, mod) % mod;
                if (hash1 == (hash2 - (s.charAt(i + len) - 'a' + base) * pow(base, len - 1, mod) % mod + mod) % mod) {
                    if (s.substring(i, i + len).equals(s.substring(i + len, i + 2 * len))) {
                        maxLen = len;
                    }
                }
                hash = hash * base - (s.charAt(i) - 'a' + base) + (s.charAt(i + len) - 'a' + base);
                hash2 = hash2 * base - (s.charAt(i) - 'a' + base) + (s.charAt(i + 2 * len) - 'a' + base);
                hash = hash % mod;
                hash2 = hash2 % mod;
            }
        }
        return s.substring(0, maxLen);
    }

    private static long pow(long a, int b, long mod) {
        long result = 1;
        while (b > 0) {
            if ((b & 1) != 0) {
                result = (result * a) % mod;
            }
            a = (a * a) % mod;
            b >>= 1;
        }
        return result;
    }
}